package com.yanceysong.codetop.s91_s100;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class S95_Mid_139_单词拆分 {
    /**
     * .S95_Mid_139_单词拆分
     * .<p>
     * .<a href="https://leetcode.cn/problems/word-break/">...</a>
     * .<p>
     * .给你一个字符串 s 和一个字符串列表 wordDict 作为字典。
     * .请你判断是否可以利用字典中出现的单词拼接出 s 。
     * .<p>
     * .注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
     * .<p>
     * .示例：
     * .<p>
     * .输入: s = "leetcode", wordDict = ["leet", "code"]
     * .输出: true
     * .解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
     * .<p>
     * .输入: s = "applepenapple", wordDict = ["apple", "pen"]
     * .输出: true
     * .解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     * .注意，你可以重复使用字典中的单词。
     * .<p>
     * .输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
     * .输出: false
     * .<p>
     * .提示：
     * .<p>
     * .1 <= s.length <= 300
     * .1 <= wordDict.length <= 1000
     * .1 <= wordDict[i].length <= 20
     * .s 和 wordDict[i] 仅由小写英文字母组成
     * .wordDict 中的所有字符串互不相同
     * .<p>
     * .核心标签：动态规划、字符串、哈希表、记忆化搜索
     * .<p>
     * .算法原理：动态规划
     * .- 定义 dp[i] 表示字符串 s 的前 i 个字符能否由字典中的单词拼接而成
     * .- 状态转移方程：dp[i] = dp[j] && wordDict.contains(s.substring(j, i))
     * .- 其中 0 <= j < i，表示如果前 j 个字符可以拼接，且 s[j:i] 在字典中，则前 i 个字符可以拼接
     * .- 初始状态：dp[0] = true（空字符串可以被拼接）
     * .- 最终答案：dp[s.length()]
     * .<p>
     * .关键洞察：
     * .1. 这是一个典型的动态规划问题，需要判断字符串能否被拆分
     * .2. 对于位置 i，需要检查所有可能的分割点 j（0 <= j < i）
     * .3. 如果 dp[j] 为 true（前 j 个字符可拼接）且 s[j:i] 在字典中，则 dp[i] = true
     * .4. 使用 HashSet 存储字典可以将查找时间优化到 O(1)
     * .5. 字典中的单词可以重复使用，这是完全背包问题的变体
     * .<p>
     * .图解示例：s = "leetcode", wordDict = ["leet", "code"]
     * .<p>
     * .字符串索引：
     * .索引:  0  1  2  3  4  5  6  7  8
     * .字符:     l  e  e  t  c  o  d  e
     * .dp值:  T  F  F  F  T  F  F  F  T
     * .<p>
     * .详细过程：
     * .<p>
     * .初始状态：
     * .dp[0] = true（空字符串）
     * .<p>
     * .i = 1: 检查 s[0:1] = "l"
     * .j = 0: dp[0]=true, "l" 不在字典中 → dp[1] = false
     * .<p>
     * .i = 2: 检查 s[0:2] = "le", s[1:2] = "e"
     * .j = 0: dp[0]=true, "le" 不在字典中
     * .j = 1: dp[1]=false, 跳过
     * .→ dp[2] = false
     * .<p>
     * .i = 3: 检查 s[0:3] = "lee", s[1:3] = "ee", s[2:3] = "e"
     * .j = 0: dp[0]=true, "lee" 不在字典中
     * .j = 1: dp[1]=false, 跳过
     * .j = 2: dp[2]=false, 跳过
     * .→ dp[3] = false
     * .<p>
     * .i = 4: 检查 s[0:4] = "leet", s[1:4] = "eet", s[2:4] = "et", s[3:4] = "t"
     * .j = 0: dp[0]=true, "leet" 在字典中！ → dp[4] = true ✓
     * .<p>
     * .i = 5: 检查 s[0:5] = "leetc", s[1:5] = "eetc", ..., s[4:5] = "c"
     * .j = 0: dp[0]=true, "leetc" 不在字典中
     * .j = 1: dp[1]=false, 跳过
     * .j = 2: dp[2]=false, 跳过
     * .j = 3: dp[3]=false, 跳过
     * .j = 4: dp[4]=true, "c" 不在字典中
     * .→ dp[5] = false
     * .<p>
     * .i = 6: 检查 s[4:6] = "co", s[5:6] = "o" 等
     * .所有组合都不满足 → dp[6] = false
     * .<p>
     * .i = 7: 检查 s[4:7] = "cod", s[5:7] = "od" 等
     * .所有组合都不满足 → dp[7] = false
     * .<p>
     * .i = 8: 检查 s[0:8] = "leetcode", ..., s[4:8] = "code"
     * .j = 0: dp[0]=true, "leetcode" 不在字典中
     * .j = 1: dp[1]=false, 跳过
     * .j = 2: dp[2]=false, 跳过
     * .j = 3: dp[3]=false, 跳过
     * .j = 4: dp[4]=true, "code" 在字典中！ → dp[8] = true ✓
     * .<p>
     * .最终结果：dp[8] = true，字符串可以被拆分
     * .<p>
     * .动态规划状态转移图：
     * .<p>
     * .""  →  "leet"  →  "leetcode"
     * .↓       ↓           ↓
     * .dp[0]  dp[4]      dp[8]
     * .true   true       true
     * .↓       ↓
     * .字典:"leet"  字典:"code"
     * .<p>
     * .另一个示例：s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
     * .<p>
     * .索引:  0  1  2  3  4  5  6  7  8  9
     * .字符:     c  a  t  s  a  n  d  o  g
     * .dp值:  T  F  F  F  T  F  F  T  F  F
     * .<p>
     * .dp[4] = true: "cats" 在字典中
     * .dp[7] = true: "cats" + "and" 在字典中
     * .dp[9] = false: 无法继续拼接（"og" 不在字典中）
     * .<p>
     * .时间复杂度：O(n^2 * .m)，其中 n 为字符串长度，m 为字典中最长单词的长度
     * .- 外层循环 O(n)
     * .- 内层循环 O(n)
     * .- substring 和 contains 操作 O(m)
     * .- 实际上，由于使用了 break 优化，平均情况会更好
     * .<p>
     * .空间复杂度：O(n + k)，其中 n 为字符串长度，k 为字典中所有单词的总长度
     * .- dp 数组：O(n)
     * .- HashSet 存储字典：O(k)
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        // 将字典转换为 HashSet，提高查找效率
        Set<String> wordDictSet = new HashSet<>(wordDict);

        // dp[i] 表示字符串 s 的前 i 个字符能否由字典中的单词拼接而成
        boolean[] canBreak = new boolean[s.length() + 1];

        // 初始状态：空字符串可以被拼接
        canBreak[0] = true;

        // 遍历字符串的每个位置
        for (int currentPos = 1; currentPos <= s.length(); currentPos++) {
            // 尝试所有可能的分割点
            for (int splitPos = 0; splitPos < currentPos; splitPos++) {
                // 如果前 splitPos 个字符可以拼接，且 s[splitPos:currentPos] 在字典中
                if (canBreak[splitPos] && wordDictSet.contains(s.substring(splitPos, currentPos))) {
                    // 则前 currentPos 个字符可以拼接
                    canBreak[currentPos] = true;
                    // 找到一种拼接方式即可，无需继续尝试其他分割点
                    break;
                }
            }
        }

        // 返回整个字符串是否可以被拼接
        return canBreak[s.length()];
    }

    public static void main(String[] args) {
        S95_Mid_139_单词拆分 solution = new S95_Mid_139_单词拆分();

        System.out.println("=== 单词拆分测试开始 ===");

        // 测试1: 题目示例1 - s = "leetcode", wordDict = ["leet", "code"]
        System.out.println("\n--- 测试1: s = \"leetcode\", wordDict = [\"leet\", \"code\"] ---");
        testCase1(solution);

        // 测试2: 题目示例2 - s = "applepenapple", wordDict = ["apple", "pen"]
        System.out.println("\n--- 测试2: s = \"applepenapple\", wordDict = [\"apple\", \"pen\"] ---");
        testCase2(solution);

        // 测试3: 题目示例3 - s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
        System.out.println("\n--- 测试3: s = \"catsandog\", wordDict = [\"cats\", \"dog\", \"sand\", \"and\", \"cat\"] ---");
        testCase3(solution);

        // 测试4: 空字符串
        System.out.println("\n--- 测试4: 空字符串 ---");
        testEmptyString(solution);

        // 测试5: 单个单词
        System.out.println("\n--- 测试5: 单个单词 ---");
        testSingleWord(solution);

        // 测试6: 字典中没有匹配的单词
        System.out.println("\n--- 测试6: 字典中没有匹配的单词 ---");
        testNoMatch(solution);

        // 测试7: 需要重复使用字典中的单词
        System.out.println("\n--- 测试7: 需要重复使用字典中的单词 ---");
        testRepeatedWords(solution);

        // 测试8: 字符串完全由一个单词组成
        System.out.println("\n--- 测试8: 字符串完全由一个单词组成 ---");
        testExactMatch(solution);

        // 测试9: 多种拆分方式
        System.out.println("\n--- 测试9: 多种拆分方式 ---");
        testMultipleSolutions(solution);

        // 测试10: 长字符串测试
        System.out.println("\n--- 测试10: 长字符串测试 ---");
        testLongString(solution);

        // 测试11: 字典中有重叠的单词
        System.out.println("\n--- 测试11: 字典中有重叠的单词 ---");
        testOverlappingWords(solution);

        // 测试12: 贪心策略会失败的情况
        System.out.println("\n--- 测试12: 贪心策略会失败的情况 ---");
        testGreedyFails(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: s = "leetcode", wordDict = ["leet", "code"]
     * .期望输出：true
     */
    private static void testCase1(S95_Mid_139_单词拆分 solution) {
        String s = "leetcode";
        List<String> wordDict = Arrays.asList("leet", "code");

        System.out.println("输入: s = \"" + s + "\", wordDict = " + wordDict);
        boolean result = solution.wordBreak(s, wordDict);
        System.out.println("输出: " + result + " (期望: true)");
        System.out.println("解释: \"leetcode\" 可以由 \"leet\" 和 \"code\" 拼接成");

        assert result : "测试1失败：期望true，实际" + result;
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: s = "applepenapple", wordDict = ["apple", "pen"]
     * .期望输出：true
     */
    private static void testCase2(S95_Mid_139_单词拆分 solution) {
        String s = "applepenapple";
        List<String> wordDict = Arrays.asList("apple", "pen");

        System.out.println("输入: s = \"" + s + "\", wordDict = " + wordDict);
        boolean result = solution.wordBreak(s, wordDict);
        System.out.println("输出: " + result + " (期望: true)");
        System.out.println("解释: \"applepenapple\" 可以由 \"apple\" \"pen\" \"apple\" 拼接成");

        assert result : "测试2失败：期望true，实际" + result;
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
     * .期望输出：false
     */
    private static void testCase3(S95_Mid_139_单词拆分 solution) {
        String s = "catsandog";
        List<String> wordDict = Arrays.asList("cats", "dog", "sand", "and", "cat");

        System.out.println("输入: s = \"" + s + "\", wordDict = " + wordDict);
        boolean result = solution.wordBreak(s, wordDict);
        System.out.println("输出: " + result + " (期望: false)");
        System.out.println("解释: 无法完整拼接出 \"catsandog\"");

        assert !result : "测试3失败：期望false，实际" + result;
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 空字符串
     * .期望输出：true
     */
    private static void testEmptyString(S95_Mid_139_单词拆分 solution) {
        String s = "";
        List<String> wordDict = Arrays.asList("a", "b");

        System.out.println("输入: s = \"\", wordDict = " + wordDict);
        boolean result = solution.wordBreak(s, wordDict);
        System.out.println("输出: " + result + " (期望: true)");
        System.out.println("解释: 空字符串可以被拼接（不需要任何单词）");

        assert result : "测试4失败：期望true，实际" + result;
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 单个单词
     * .期望输出：true
     */
    private static void testSingleWord(S95_Mid_139_单词拆分 solution) {
        String s = "hello";
        List<String> wordDict = Arrays.asList("hello", "world");

        System.out.println("输入: s = \"" + s + "\", wordDict = " + wordDict);
        boolean result = solution.wordBreak(s, wordDict);
        System.out.println("输出: " + result + " (期望: true)");
        System.out.println("解释: \"hello\" 本身就在字典中");

        assert result : "测试5失败：期望true，实际" + result;
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 字典中没有匹配的单词
     * .期望输出：false
     */
    private static void testNoMatch(S95_Mid_139_单词拆分 solution) {
        String s = "hello";
        List<String> wordDict = Arrays.asList("world", "java");

        System.out.println("输入: s = \"" + s + "\", wordDict = " + wordDict);
        boolean result = solution.wordBreak(s, wordDict);
        System.out.println("输出: " + result + " (期望: false)");
        System.out.println("解释: 字典中没有能拼接出 \"hello\" 的单词");

        assert !result : "测试6失败：期望false，实际" + result;
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 需要重复使用字典中的单词
     * .期望输出：true
     */
    private static void testRepeatedWords(S95_Mid_139_单词拆分 solution) {
        String s = "aaaaaaa";
        List<String> wordDict = Arrays.asList("aa", "aaa");

        System.out.println("输入: s = \"" + s + "\", wordDict = " + wordDict);
        boolean result = solution.wordBreak(s, wordDict);
        System.out.println("输出: " + result + " (期望: true)");
        System.out.println("解释: 可以由 \"aa\" + \"aa\" + \"aaa\" 或其他组合拼接成");

        assert result : "测试7失败：期望true，实际" + result;
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 字符串完全由一个单词组成
     * .期望输出：true
     */
    private static void testExactMatch(S95_Mid_139_单词拆分 solution) {
        String s = "programming";
        List<String> wordDict = Arrays.asList("programming", "code");

        System.out.println("输入: s = \"" + s + "\", wordDict = " + wordDict);
        boolean result = solution.wordBreak(s, wordDict);
        System.out.println("输出: " + result + " (期望: true)");
        System.out.println("解释: \"programming\" 完全匹配字典中的单词");

        assert result : "测试8失败：期望true，实际" + result;
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 多种拆分方式
     * .期望输出：true
     */
    private static void testMultipleSolutions(S95_Mid_139_单词拆分 solution) {
        String s = "catsanddog";
        List<String> wordDict = Arrays.asList("cat", "cats", "and", "sand", "dog");

        System.out.println("输入: s = \"" + s + "\", wordDict = " + wordDict);
        boolean result = solution.wordBreak(s, wordDict);
        System.out.println("输出: " + result + " (期望: true)");
        System.out.println("解释: 可以拼接为 \"cats\" + \"and\" + \"dog\" 或 \"cat\" + \"sand\" + \"dog\"");

        assert result : "测试9失败：期望true，实际" + result;
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 长字符串测试
     * .期望输出：true
     */
    private static void testLongString(S95_Mid_139_单词拆分 solution) {
        String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        List<String> wordDict = Arrays.asList("a", "aa", "aaa", "aaaa", "aaaaa");

        System.out.println("输入: s = \"" + "a".repeat(100) + "\" (100个a), wordDict = [\"a\", \"aa\", \"aaa\", \"aaaa\", \"aaaaa\"]");
        boolean result = solution.wordBreak(s, wordDict);
        System.out.println("输出: " + result + " (期望: true)");
        System.out.println("解释: 可以由多个 \"a\" 拼接成");

        assert result : "测试10失败：期望true，实际" + result;
        System.out.println("✓ 测试10通过");
    }

    /**
     * .测试11: 字典中有重叠的单词
     * .期望输出：true
     */
    private static void testOverlappingWords(S95_Mid_139_单词拆分 solution) {
        String s = "abcd";
        List<String> wordDict = Arrays.asList("a", "abc", "b", "cd");

        System.out.println("输入: s = \"" + s + "\", wordDict = " + wordDict);
        boolean result = solution.wordBreak(s, wordDict);
        System.out.println("输出: " + result + " (期望: true)");
        System.out.println("解释: 可以拼接为 \"abc\" + \"d\" 或 \"a\" + \"b\" + \"cd\"");

        assert result : "测试11失败：期望true，实际" + result;
        System.out.println("✓ 测试11通过");
    }

    /**
     * .测试12: 贪心策略会失败的情况
     * .期望输出：true
     */
    private static void testGreedyFails(S95_Mid_139_单词拆分 solution) {
        String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        List<String> wordDict = Arrays.asList("a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa");

        System.out.println("输入: s = \"" + "a".repeat(139) + "b\" (139个a + 1个b), wordDict = [\"a\", \"aa\", ..., \"aaaaaaaaaa\"]");
        boolean result = solution.wordBreak(s, wordDict);
        System.out.println("输出: " + result + " (期望: false)");
        System.out.println("解释: 无法拼接出最后的 \"b\"");

        assert !result : "测试12失败：期望false，实际" + result;
        System.out.println("✓ 测试12通过");
    }
}

